class Solution {//leetcode91——解码方法
public:
    int numDecodings(string s) {
        //创建dp表，并且填充dp[0],dp[1]
        int n=s.size();
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=s[0]!='0';
        //状态表示为，在i位置上，编码的总数
        //状态方程为：dp[i]=dp[i-1]+dp[i-2]。
        for(int i=2;i<=n;i++){
            if(s[i-1]!='0') dp[i]+=dp[i-1];
            int t=(s[i-2]-'0')*10+s[i-1]-'0';
            if(t<=26&&t>=10) dp[i]+=dp[i-2];
        }
        return dp[n];
    }
};